package com.datastructures.hashtable;

import java.util.Scanner;

/**
 * @author MaoLin Wang
 * @date 2019/11/210:07
 */
public class HashTableDemo {
    public static void main(String[] args) {

        HashTable hashTable = new HashTable(7);

        String key="";
        Scanner scanner = new Scanner(System.in);
        while (true){
            System.out.println("add:添加");
            System.out.println("list:显示列表");
            System.out.println("exit:退出");
            key = scanner.next();
            switch (key){
                case "add":
                    System.out.println("输入id");
                    int id=scanner.nextInt();
                    System.out.println("输入名字");
                    String name=scanner.next();
                    Person person = new Person(id, name);
                    hashTable.add(person);
                    break;
                case "list":
                    hashTable.list();
                    System.out.println();
                    break;
                case "find":
                    System.out.println("请输入要查找的id");
                    id=scanner.nextInt();
                    hashTable.findById(id);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                default:
                    break;
            }

        }
    }
}


class Person {
    public int id;
    public String name;
    public Person next;

    public Person(int id, String name) {
        this.id = id;
        this.name = name;
    }
}

class PersonLinkedList {
    //头指针执行第一个Emp,因此链表的head直接指向第一个Emp
    private Person head;

    /**
     * 1.id自增
     * 2.将员工直接添加到最后
     * @param person
     */
    public void add(Person person){

        if (head==null){
            head= person;
            return;
        }
        Person temp = head;
        while (true){
            if (temp.next == null){
                break;//到达链表最后
            }
            temp = temp.next;
        }
        //添加到尾部
        temp.next = person;
    }

    public void print(int num){
        if (head==null){
            System.out.println("链表"+(num+1)+"为空");
            return;
        }
        Person temp=head;
        while (true){

            if (temp == null){
                break;
            }
            System.out.println("链表"+(num+1)+"的信息为==>  id=>"+temp.id+":"+"name=>"+temp.name);

            temp=temp.next;
        }
        System.out.println();
    }

    public Person findByid(int id){
        if (head==null){
            System.out.println("链表为空");
            return null;
        }
        Person temp= head;
        while (true){
            if (temp.id==id){
                //找到
                break;
            }
            if (temp.next==null){
                //未找到
                temp=null;
                break;
            }
            temp=temp.next;
        }
        return temp;
    }
}

//创建HashTable
class HashTable {
    private int size; //多少条链表
    private PersonLinkedList[] personLinkedLists;

    public HashTable(int size) {
        this.size=size;
        personLinkedLists=new PersonLinkedList[size];
        for (int i =0;i<size;i++){
            //初始化每个链表
            personLinkedLists[i]=new PersonLinkedList();
        }
    }

    public void add(Person person){
        //根据id得到其该添加到哪个链表
        int personLinkedListNo = sanlie(person.id);
        //添加到对应链表
        personLinkedLists[personLinkedListNo].add(person);

    }
    //遍历Hash链表
    public void list(){
        for (int i = 0;i < size; i++){
            personLinkedLists[i].print(i);
        }
    }

    //根据id查找
    public void findById(int id){
        int listNo = sanlie(id);
        Person person = personLinkedLists[listNo].findByid(id);
        if (person !=null){
            System.out.println("在第"+(listNo+1)+"个链表找到:"+"id:"+person.id+"name："+person.name);

        }else {
            System.out.println("未找到目标");
        }
    }

    //散列函数(取模法)
    public int sanlie(int id){
        return id % this.size;
    }
}